//https://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993?tpId=13&tqId=23288&ru=%2Fpractice%2F6aa9e04fc3794f68acf8778237ba065b&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思想：排序问题的变种：选择排序；
//思想：利用std::sort 实现排序；

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution1 {
  public:
    string PrintMinNumber(vector<int> numbers) {
        if (numbers.empty()) return "";
        //选择排序，从小到大排好序。
        for (int i = 0; i < numbers.size() - 1; ++i) {
            int minIndex = i;
            for (int j = i + 1; j < numbers.size(); ++j) {
                if (CompareTwoValueSmall(numbers[j], numbers[minIndex])) {
                    minIndex = j;
                }
            }
            std::swap(numbers[i], numbers[minIndex]);
        }
        std::string t_str = "";
        for (int z = 0; z < numbers.size(); ++z) {
            t_str += std::to_string(numbers[z]);
        }
        return t_str;

    }

    bool CompareTwoValueSmall(int a, int b ) {

        auto str_a = std::to_string(a);
        auto str_b =  std::to_string(b);

        std::string ab = str_a + str_b;
        std::string ba = str_b + str_a;
        return ab < ba;
    }
};

class Solution2 {
  public:
    //重载排序比较方式
    static bool cmp(string& x, string& y) {
        //叠加
        return x + y < y + x;
    }
    string PrintMinNumber(vector<int> numbers) {
        string res = "";
        //空数组的情况
        if (numbers.size() == 0)
            return res;
        vector<string> str_vec;
        str_vec.reserve(numbers.size());
        //将数字转成字符
        for (int i = 0; i < numbers.size(); i++){
            str_vec.emplace_back(std::to_string(numbers[i]));
        }
        //排序
        std::sort(str_vec.begin(), str_vec.end(), [](string& s1,string& s2) { return s1+s2<s2+s1;});
        //字符串叠加
        for (int i = 0; i < str_vec.size(); i++)
            res += str_vec[i];
        return res;
    }
};